from typing import *
import random


class Solution:

    def findKthLargest(self, nums: List[int], k: int) -> int:

        def find(nums, l, r, rdm):
            nums[rdm], nums[r] = nums[r], nums[rdm]  # 放到右边界
            num = nums[r]
            k = l
            for i in range(l, r):  # 右边界不参与
                if nums[i] < num:
                    nums[i], nums[k] = nums[k], nums[i]  # 小于rdm位置的数放到左侧
                    k += 1
            nums[k], nums[r] = nums[r], nums[k]  # 换回来
            return k

        def findk(nums, l, r, k):
            rdm = random.randrange(l, r + 1)
            idx = find(nums, l, r, rdm)
            curk = r + 1 - idx
            if curk == k:  # 找到第k大
                return nums[idx]
            elif curk < k:
                return findk(nums, l, idx - 1, k - curk)  # k小了，目标在左边
            else:
                return findk(nums, idx + 1, r, k)

        return findk(nums, 0, len(nums) - 1, k)


s = Solution()
print(s.findKthLargest([3, 2, 1, 5, 6, 4], 2))
print(s.findKthLargest([3, 2, 1, 5, 6, 4], 1))
print(s.findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))
